package com.zdp.leetcodeMiddle;


import com.zdp.util.TreeNode;

import java.util.*;

/*
* 题目描述：
* 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，
* 最近公共祖先表示为一个节点 x，
* 满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
示例 1：
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出：3
解释：节点 5 和节点 1 的最近公共祖先是节点 3 。
示例 2：
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出：5
解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。
示例 3：
输入：root = [1,2], p = 1, q = 2
输出：1 
提示：
树中节点数目在范围 [2, 105] 内。
-109 <= Node.val <= 109
所有 Node.val 互不相同 。
p != q
p 和 q 均存在于给定的二叉树中

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
* */
public class 二叉树的最近公共祖先_236 {

    /*
    * 解题思路 ： 利用递归
    * */
    private TreeNode result = null;
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        f(root,p,q);
        return result;
    }

    public boolean f(TreeNode root,TreeNode p,TreeNode q){
        if( root == null){
            return false;
        }
        boolean lson = f(root.left,p,q); // 判断当前节点的左子树 是否包含 p 或者 q节点
        // 判断当前节点的 右子树 是否包含 p 或者 q节点
        boolean rson = f(root.right,p,q);
        // 判断当前节点是否为 最近公共祖先
        if( (lson && rson) ||
                ( (root.val == p.val || root.val == q.val) && (lson || rson)) ){
            // 当前节点为 公共祖先的 条件有 ：
            /*
            *  当前节点的 左子树和右子树包含q节点 或者 p节点
            * 或者 当前节点 为 p节点 或者 q节点，其左子树或者右子树 包含另外的一个节点
            * */
            result = root;
        }
        return lson || rson || (root.val == p.val || root.val == q.val);
    }

    /*
    * 利用 哈希表 记录每个节点的父节点
    * */
    public TreeNode lowestCommonAncestor1(TreeNode root, TreeNode p, TreeNode q){
        Map<TreeNode,TreeNode>  father = new HashMap<>();
        LinkedList<TreeNode> queue = new LinkedList<>();
        father.put(root,null);
        queue.add(root);
        while(!queue.isEmpty()){
            TreeNode fa = queue.pollFirst();
            // 记录父亲节点
            if(fa.left != null){
                father.put(fa.left,fa);
                queue.add(fa.left);
            }
            if(fa.right != null){
                father.put(fa.right,fa);
                queue.add(fa.right);
            }
        }
        // 记录完毕后
        // 记录 p 的所有祖先
        Set<Integer> only = new HashSet<>();
        while(p!=null){
            only.add(p.val);
            p = father.get(p);
        }
        // 找 公共祖先
        while(q!=null){
            if(only.contains(q.val)){
                return q;
            }
            q = father.get(q);
        }
        return null;
    }
}
